This invention relates to computer systems, and more particularly to multi-tasking.
The purpose of the invention is to increase the efficiency and flexibility of the execution of several tasks at once. Task scheduling is an important part of a modern computer system because it can have a large effect on performance. Presently, most task scheduling models fall into one of two general categories: preemptive multitasking and cooperative multitasking.
Preemptive multitasking is driven by allocating fixed amounts of processing time to each running task and saving and restoring all the necessary state information at the beginning and end of each time period. This saving and restoring process is known as a context switch. Because these context switches can occur at times when a process is in the middle of a number of operations, the amount of information saved and restored during a context switch can be very high. However, preemptive multitasking can ensure that no process takes time away from other processes or prevents other processes from running.
Cooperative multitasking relies on each process to voluntarily yield control of a processor to other tasks, typically to a scheduler that then transfers control to the next available task. Cooperative multitasking has the potential to be far more efficient than preemptive multitasking, since applications can be written to yield control in such a way that the number of context switches is minimized and at times when minimal context needs to be saved so that context switches that do occur will be much faster. However, improperly written or malicious code can cause cooperative multitasking to result in slow responses to external inputs or worse, the starvation of other tasks. Because of these impediments, preemptive multitasking has become the model of choice for most modern general-purpose operating systems and systems that require real-time performance.
What is needed is a way to combine the efficiency benefits of cooperative multitasking with the responsiveness of preemptive multitasking. Prior art attempts to do this have used both types of systems running simultaneously or one system running on top of the other, to allow the appropriate form of multitasking to be used for the appropriate category of tasks. However, this requires complex synchronization mechanisms (U.S. Pat. No. 6,148,325) and still requires a significant amount of context switching. In addition, the added complexity results in additional performance overhead (U.S. Pat. No. 6,223,201). It is highly desirable to reduce this overhead and the overhead of context switching.
Normally when a task scheduler executes on a data processor, it picks a task and calls the task for execution. When the task yields its time under a cooperative multitasking system or when a set amount of time has expired under a preemptive multitasking system, the scheduler is called again, at which point it calls the next task to execute. However, the overhead involved in returning control to the scheduler between each task adds a significant amount of time to each context switch. Furthermore, since most operating system schedulers execute in kernel mode, most operating system tasks must switch the processor to and from kernel mode as part of every context switch. Therefore, it is highly desirable to find a means for avoiding the additional overhead incurred by having the scheduler called during each context switch.
A large amount of prior art has attempted to reduce the amount of time required for context switches, by reducing the number of context switches that typically occur or by reducing the length of time of each context switch (U.S. Pat. No. 6,314,510 and Engler, D. R., Kaashoek, M. F., O'Toole, J. Jr., “Exokernel: an operating system architecture for application-specific resource management,” Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995). The most effective prior art solutions require modifications to the hardware (U.S. Pat. No. 6,209,085), modifications of the tasks themselves, or specific hardware dependencies (Leidke, J., Elphinstone, K., Schnberg, S., Hrtig, H., Heiser, G., Islam, N., Jaeger, T., “Achieved IPC Performance,” Proceedings of the Sixth Workshop on Hot Topics in Operating Systems, pp. 28–31, Cape Cod, Mass., May 1997). It is therefore desirable to achieve a significant reduction of context switch time transparently to the task author and user in a hardware-independent manner. It is also desirable to further decrease the overhead of context switching beyond the advancements of the prior art.
Some virtual machine and dynamic code generation prior art (Poletto, M., Hsieh, W. C., Engler, D. R., Kaashoek, M. F., “C and tcc: A language and compiler for dynamic code generation,” ACM Transactions on Programming Languages and Systems 21(2), pp. 324–369, March 1999) has shown promise in performing optimizations on code. However, this prior art does not significantly reduce the amount of context switching, and actually increases the total amount of overhead to multitasking in most cases. Furthermore, the most effective prior art requires extensive modifications to the tasks by a skilled developer (Engler, D. R., “VCODE: a retargetable, extensible, very fast dynamic code generation system,” Proceedings of the ACM SIGPLAN '96 Conference on Programming Design and Implementation (PLDI '96), Philadelphia, Pa., pp. 160–170, May 1996). It is therefore desirable to provide a means for optimizing code through the dynamic generation of code based on pre-existing tasks without requiring the developer or user to intervene.